/*
 * @Author: liusheng
 * @Date: 2022-04-07 16:02:59
 * @LastEditors: liusheng
 * @LastEditTime: 2022-04-08 21:20:27
 * @Description: 
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 */

#include <string>
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int len = s.size();
        if (len < 1)
        {
            return 0;
        }

        unordered_set<char> cnt;
        int maxLen = 0;
        int end = -1;
        for(int start = 0; start < len; ++start)
        {
            //erase the left
            if (start != 0)
            {
                cnt.erase(s[start-1]);
            }

            //add to cnt until show repeat
            //start-end is not repeated,end + 1 has repeated value
            //keep the end index is the most right index which not repeated
            while(end + 1 < len && cnt.count(s[end + 1]) == 0)
            {
                cnt.insert(s[end + 1]);
                ++end;
            }

            // printf("start= %d,end=%d\n",start,end);

            int len = end - start + 1;
            if (len > maxLen)
            {
                maxLen = len;
            }
        }

        return maxLen;
    }

    int lengthOfLongestSubstring1(string s)
    {
        int n = s.size();
        if ( n < 1)
        {
            return 0;
        }
        
        //record character last show up index in s
        vector<int> cnt(256,-1);
        int maxLen = 0;
        int charLastShowIndex = -1;
        for (int i = 0; i < n; ++i)
        {
            //charLastShowIndex:current character last show index 
            //works when character repeated with last,such as "aab"
            if (cnt[s[i]] > charLastShowIndex)
            {
                charLastShowIndex = cnt[s[i]];
            }
            
            cnt[s[i]] = i;
            int len = i - charLastShowIndex;
            
            maxLen = len > maxLen ? len : maxLen;            
        }
        
        return maxLen;
    }
};